/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class KeysKeyboard2 {
    public int maxA(int N) {
    	if(N<7){
    		return N;
    	}
        int[] dp=new int[N+1];
        for(int i=0;i<7;i++){
        	dp[i]=i;
        }
        for (int i = 7; i <= N; i++) {
        	dp[i]=dp[i-1]+1;
        	for (int k = 1; k < i-2; k++) {
				dp[i]=Integer.max(dp[i], (1+k)*dp[i-k-2]);
			}
        }
        return dp[N];
    }

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		KeysKeyboard2 keyboard = new KeysKeyboard2();
		for (int i = 1; i < 1000; i++) {
			System.out.println(keyboard.maxA(i));
		}
	}

}
